package leetcode

import (
	"fmt"
	"math"
)

// TreeNode treenode
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// ToString Traverse tree node
func (node *TreeNode) ToString() {
	if node == nil {
		return
	}
	fmt.Printf("%d\t", node.Val)
	if node.Left != nil {
		node.Left.ToString()
	}
	if node.Right != nil {
		node.Right.ToString()
	}
}

func minDepth(node *TreeNode) float64 {
	if node == nil {
		return 0
	}
	left := minDepth(node.Left)
	right := minDepth(node.Right)

	height := math.Min(left, right)
	if left == 0 || right == 0 {
		height = left + right
	}
	return height + 1
}

// MinDepth MinDepth
func MinDepth(root *TreeNode) int {
	return int(minDepth(root))
}

func hasPath(node *TreeNode, sum int, presum int) bool {
	if node == nil {
		return false
	}
	cursum := presum + node.Val

	l := hasPath(node.Left, sum, cursum)
	if l {
		return true
	}
	r := hasPath(node.Right, sum, cursum)
	if r {
		return true
	}
	if node.Right == nil && node.Left == nil {
		if cursum == sum {
			return true
		}
	}
	return false
}

func hasPathSum(node *TreeNode, sum int) bool {
	if node == nil {
		return false
	}

	return hasPath(node, sum, 0)
}

func printPath2(stack []int) {
	fmt.Println()
	for _, v := range stack {
		fmt.Printf(" %v ->", v)
	}
	fmt.Println()
}

func hasPath2(node *TreeNode, sum int, presum int, path []int, allPath *[][]int) {
	if node == nil {
		return
	}

	path = append(path, node.Val)
	cursum := presum + node.Val

	hasPath2(node.Left, sum, cursum, path, allPath)
	hasPath2(node.Right, sum, cursum, path, allPath)

	if node.Right == nil && node.Left == nil {
		if cursum == sum {
			printPath2(path)
			tmpPath := make([]int, len(path))
			copy(tmpPath, path)
			*allPath = append(*allPath, tmpPath)
		}
	}
	return
}

// PathSum2 PathSum2
func PathSum2(root *TreeNode, sum int) [][]int {
	allPath := make([][]int, 0)
	path := make([]int, 0)
	hasPath2(root, sum, 0, path, &allPath)
	return allPath
}

func printPath3(path []*TreeNode) {
	fmt.Println()
	for _, v := range path {
		fmt.Printf(" %v ->", v.Val)
	}
	fmt.Println()
}

func calcPath3(path []*TreeNode, sum int) int {
	pathsum := 0
	count := 0
	for i := len(path) - 1; i >= 0; i-- {
		pathsum += path[i].Val
		if pathsum == sum {
			count++
		}
	}
	return count
}

func pathSum3(node *TreeNode, sum int, path []*TreeNode) int {
	if node == nil {
		return 0
	}

	path = append(path, node)

	lcount := pathSum3(node.Left, sum, path)
	rcount := pathSum3(node.Right, sum, path)
	curCount := calcPath3(path, sum)

	return lcount + rcount + curCount
}

// PathSum3 path sum
func PathSum3(root *TreeNode, sum int) int {
	path := make([]*TreeNode, 0)
	return pathSum3(root, sum, path)
}
